#include <iostream>
#include <stack>

using namespace std;

struct BSTreeNode // a node in the binary search tree (BST)
{
	int          m_nValue; // value of node
	BSTreeNode  *m_pLeft;  // left child of node
	BSTreeNode  *m_pRight; // right child of node
};

void MirrorRecursively(BSTreeNode *pNode)
{
	if(pNode == NULL)
		return;
	if(pNode->m_pLeft || pNode->m_pRight)
	{
		struct BSTreeNode *temp = pNode->m_pLeft;
		pNode->m_pLeft = pNode->m_pRight;
		pNode->m_pRight = temp;
	}

	MirrorRecursively(pNode->m_pLeft);
	MirrorRecursively(pNode->m_pRight);
}

void MirrorIteratively(BSTreeNode *pTreeHead)
{
	if(!pTreeHead)
		return;
	stack<BSTreeNode *> s;
	s.push(pTreeHead);
	while(!s.empty())
	{
		BSTreeNode *top = s.top();
		s.pop();
		if(top->m_pLeft || top->m_pRight)
		{
			BSTreeNode *temp = top->m_pLeft;
			top->m_pLeft = top->m_pRight;
			top->m_pRight = temp;
		}
		if(top->m_pLeft)
			s.push(top->m_pLeft);
		if(top->m_pRight)
			s.push(top->m_pRight);
	}
}

void _print(BSTreeNode *pNode)
{
	if(!pNode)
		return;
	
	_print(pNode->m_pLeft);
	cout<<pNode->m_nValue<<" ";
	_print(pNode->m_pRight);
}

void print(BSTreeNode *pNode)
{
	_print(pNode);
	cout<<endl;
}

int main()
{
	struct BSTreeNode a8, a6, a10, a5, a7, a9 ,a11;

	a8.m_nValue = 8;
	a8.m_pLeft = &a6;
	a8.m_pRight = &a10;

	a6.m_nValue = 6;
	a6.m_pLeft = &a5;
	a6.m_pRight = &a7;

	a10.m_nValue = 10;
	a10.m_pLeft = &a9;
	a10.m_pRight = &a11;

	a5.m_nValue = 5;
	a5.m_pLeft = NULL;
	a5.m_pRight = NULL;

	a7.m_nValue = 7;
	a7.m_pLeft = NULL;
	a7.m_pRight = NULL;

	a9.m_nValue = 9;
	a9.m_pLeft = NULL;
	a9.m_pRight = NULL;

	a11.m_nValue = 11;
	a11.m_pLeft = NULL;
	a11.m_pRight = NULL;

	cout<<"init"<<endl;
	print(&a8);
	MirrorRecursively(&a8);
	cout<<"MirrorRecursively"<<endl;
	print(&a8);
	MirrorRecursively(&a8);
	cout<<"MirrorRecursively"<<endl;
	print(&a8);
	MirrorIteratively(&a8);
	cout<<"MirrorIteratively"<<endl;
	print(&a8);
}
